1

[CERC2017] Buffalo Barricades

考虑算出每个点最终被哪个矩形包含,这种情况下只有相互交叉的两个矩形可能存在覆盖关系。

此时交叉在 y 轴上只有一种体现,那就是比一条线靠后的射线,被这条射线在 y 轴上恰好覆盖。

因此按矩形的 x 坐标降序扫描线,用 set 维护射线的端点。因为矩形之间是编号小的覆盖在上面,所以考虑加入一条新的射线,如果被这条射线覆盖到的端点里面,有一个编号比它大,那么应当删除这个端点。

set 维护的实际上是这样一个结构:

最终导致的结果,应当是端点在当前线之前的射线,编号都比当前线小。那么考虑一个点属于的矩形,就是覆盖这个点的那条射线。

考虑这样计算,只存在一种情况的矩形没办法准确计算答案,就是矩形 A 包含矩形 B,且矩形 A 比矩形 B 早出现。

考虑最后加入的矩形,答案一定是正确计算的。而一个没有被正确计算答案的矩形一定较早出现。

按照加入顺序倒序遍历所有矩形,那么找到在最终图形上,包含掉这个矩形的矩形,这只有一个,把答案合并到这上面即可。

[HNOI2018] 排列

注意这个限制并不等价于反串的字典序最大!!能转化到字典序模型需要一个“绝对优势”。

考虑一段序列 A 后面接序列 B,代价是:

i=1|A|(pre+i)wi+i=1|B|(pre+|A|+i)wi

反过来的话,代价是:

i=1|B|(pre+i)wi+i=1|A|(pre+|B|+i)wi

AB 前面,就等价于 |B|i=1|A|wi+|A|i=1|B|wi>01|A|i=1|A|wi<1|B|i=1|B|wi

对于确定的树形拓扑序,如果可以比较两个段哪个放在前面更好的话,一种通用的贪心方式就是每次找到最优的那个段,把它往父亲合并。

这样就有复杂度 O(nlogn)

扩展 KMP 复习

ss,t 的每个后缀的 LCP。

定义 z[i]=LCP(s,s[i:]]),p[i]=LCP(s,t[i:]),维护当前匹配出的最靠后的一段 Border s[l,r]=s[:rl+1],那么如果 ir,可以发现有:

直接向后暴力更新就是 O(n)

.

2

[CF780F] Axel and Marston in Bitland & [NOI2020] 美食家

考虑构造矩阵 FT=|f[T,1]...f[T,n]|,其中 f[T,i] 表示第 T 天在城市 i 的最大价值。

考虑转移矩阵就是邻接矩阵 W,其中 Wi,j 表示:

考虑一次美食节,等价于第 ti 天的转移矩阵发生变化,记为 Wi,等于把 W 的列向量 xi 整体加 yi

max+ 矩阵乘法满足结合律,但是没有交换律,最终的转移矩阵形式是 Wt11W1Wt2t11W2...

这样朴素做是 O(k(5m)3logT),应该能有 35pts。预处理快速幂矩阵应该可以显著减小常数,但是这不本质。

考虑直接 DP 的复杂度是 O(Tn2),那么如果数据分治 T52501,应该有 40pts+25pts=65pts。

特殊性质 A 非常好做,这样应该就有 75pts。

如果对每个点新建五个点,就是 O(k(5n)3logT). 75pts.

因为最终结果只需要第一行,如果我们始终维护一个 1×n 的矩阵做乘法,那么每次乘法实际上是 O(n2) 的,这里复杂度瓶颈在于算快速幂时乘法是 O(n3) 的。

预处理 2k 处的矩阵,那么总复杂度就是 O((5n)3logT+(5n)2klogT)

[CODE FEST 2016 Grand Final] Water Distribution

对于一个块考虑,它最后整体的和一定是所有点权减掉用过的所有边权,那么最大化这个东西显然需要最小化用过的边权和,那么可以发现这个就是 MST 的边权和。

对每个可能的块预处理,复杂度 O(2npoly n)

最后需要若干个块拼起来,这个直接就 O(3n) 枚举子集转移即可。

[51nod 1832] 后序与先序遍历

一棵二叉树如果某个节点只有一个儿子,那么无论这个儿子是它的左儿子或者右儿子,这棵树的先序遍历和后序遍历都是不变的。

先序遍历中 p[pos[i]+1] 一定是 i 的左儿子,后序遍历中 p[pos[i]1] 一定是 i 的右儿子。除非不存在,此时 p[pos[i]+1]=p[pos[i]1]

设只有一个儿子的节点数量为 cnt,那么答案就是 2cnt

[51nod 1231] 记分牌

竞赛图的一个得分合法,等价于对所有 k,前 k 小的得分之和 (k2)

[CF1303F] Number of Components

考虑如果正着做,唯一无法用并查集处理的问题是断掉两个联通块。

如果把这个过程反过来看,又相当于合并两个联通块,因此正反都做一遍即可。

cici+1 保证了一个联通块至多进行一次断边或连边操作,因此是正确的。

细节???

.

3

高斯消元求自由元

[POJ1830] 开关问题

考虑按每个变量列方程,然后高斯消元,判断每个方程的主元是否存在即可求出自由元数量。

在实现上,由于可能无法消元成恰好的对角线矩阵,因此需要倒着枚举变量,回代方程。

O(n3ω).

[HAOI2018] 反色游戏

考虑有 m 个变量,n 条方程,模 2 意义,求可能的解的数量。设自由元数量是 cnt,显然答案是 2cnt

XOR方程组的求解

求解 n 条方程,m 个变量的异或方程组。

定义一个指针 p 指向最后一个确定了主元的方程的位置 +1。顺序枚举变量 i[1,m],试图找到一个方程,并把这个方程的主元置为变量 i

如果找不到,那么显然 i 是自由元。否则,设这样的位置是 q,那么多了一条确定主元的方程,我们把它放在第 p 个位置上,然后向下消元。

这样我们可以得到一个近似的上三角矩阵,其中第 p 条方程的主元是其第一个满足 a[p,i]=1 的变量 i,并且满足后 np+1 条方程都是无效的方程。

然后考虑回代过程,那么先枚举无效方程,此时方程右边的系数必须为 0,否则意味着方程组无解。

然后倒序枚举有主元的方程,我们总能解出该方程的主元的取值,然后向上回代即可。

O(m2nω)

这样就有 60pts。

[HAOI2018] 染色

f[k] 表示出现 S 次的颜色恰有 k 种的方案数,g[k] 表示钦点 k 种颜色出现 S 次的方案数。

答案是:i=0MWif[i]

显然有:g[k]=i=kM(ik)f[i]

那么:f[k]=i=kM(1)ik(ik)g[i]

g[i]=(Mi)N!(S!)i(NiS)!(Mi)NiS

f[k]=i=kM(1)ik(ik)(Mi)N!(S!)i(NiS)!(Mi)NiS

=N!M!k!i=0Mk(1)ii!×(M(i+k))N(i+k)S(M(i+k))!(S!)i+k(N(i+k)S)!

构造 a[i]=(1)ii!,b[i]=(Mi)NiS(Mi)!(S!)i(NiS)!,长度均为 M

f[k]=N!M!k!i=0Ma[i]b[i+k]

随便 reverse 即可 O(nlogn).

[Gym - 102978B] Bit Operation

考虑等价于每次选相邻的两个点,然后删掉其中一个。

枚举最后保留下来的点是哪个,那么考虑前后的点必须删掉,显然这个的方案数只和序列长度相关。

考虑枚举最后一次操作删掉了哪个点,如果当前长度为 i,那么有 2(i1) 种方案先选择一对点然后再选出一个点,其中一种方案是不可行的,因此有 f[n]=f[n1](2n3)

考虑最后前后的操作序列,只需要考虑相对顺序不变来拼接,有组合数系数 (n1i1)

LGV 引理

在一张 DAG 上,有 n 个起点和 n 个终点。建立一个起点和终点之间的双射 st,问有多少路径集合 {(ui,vi)} 满足 ui=si,vi=ti,且路径之间两两不相交。

如果这张 DAG 具备特殊性质,满足有且仅有一种双射能找到合法解,定义邻接矩阵 G 满足 Gi,j 表示从 i 起点到 j 终点的路径条数,那么解的数量是 det G

.

4

[NOI2018] 你的名字

考虑如果询问是整串,那么我们只需要用 S 的 SAM 读入 T,维护一下当前读入的长度 T[pos:i],那么新增的贡献是 ipos+1

考虑每次跳 nxt[] 均会删掉 T 当前读入的一段前缀,因此这样的复杂度是 O(|T|) 的。

如果询问不是整串,那么只需要知道,某条树边是否存在。只需要维护这条边到达节点的 endpos,就可以知道 S[l:r] 中是否有这个串,也就可以判断这条边是否存在。

[HAOI2018] 字串覆盖

考虑这样一个新的问题:给定串 S,T,求 T[l:r]S[s:t] 中第一次出现的位置。

考虑建立广义前缀树,找到 T[l:r] 在前缀树上对应的节点,维护 Sendpos 集合,我们只需要在线段树上二分即可。

那么只需要每次暴力寻找下一个即是 O(nlogn|T|),考虑数据分治一下瞎搞就做完了,垃圾题。

[HAOI2018] 奇怪的背包

需要注意到一个非常重要的事情:所有有效数字都应当是 P 的因子,而 P 的因子并不是很多。

首先把 a[i] 变成 (a[i],P),那么答案不改变,去重以后,选一个因子有 2s1 种方法。

直接对着 P 的因子 DP,最后暴力枚举两个因子合并答案,复杂度 O(σ0(P)2logP)O(1)

[HAOI2018] 苹果树

给点第 i 次操作的点标号 i,然后考虑枚举一个点,算这个点上面那条边的贡献,就是 sz[i](nsz[i])

考虑枚举 sz[i],然后算方案数。前面构造到 ii! 种方案,后面还剩 ni 次操作。先选出 i 的子树,显然是 (nisz[i]1)sz[i]!,然后后面的点不能选在 i 的子树里,应当是 (i1)nisz[i]+1,这部分乘起来就是:

i!(i1)nisz[i]+1(nisz[i])sz[i]!=sz[i]!(nisz[i]1)(nsz[i]1)!i(i1)

答案是:

i=2ni(i1)s=1n1(nis1)s·s!(ns)!

应该可以卷积。

[JSOI2019] 节日庆典

我们知道对于最小表示法问题,有一个 O(n) 的 lyndon 分解解法:

这样做就是 O(n2) 的,可以拿到 30pts 的好成绩。

先考虑一个错误的贪心:取字典序最小的后缀。这个贪心的错因在于接上前缀之后,字典序可能会变大,但是这启发我们,有用的后缀是字典序最小的那些后缀。

形式化地,我们定义一个后缀 s[i:] 有用,当且仅当仅不存在一个后缀严格小于它。这里 s 严格小于 t 指可以找到一个位置 p[1,min|s|,|t|],使得 sp<tps[1:p1]=t[1:p1]

可以发现,如果相邻的两个有用的后缀中,后面那个到前面那个的距离小于后面的串长,那么后面的那个没有用处。这说明了有用的后缀数量是 O(logn) 的。

考虑维护有用的后缀构成的集合 S,记对于前缀 i,维护出的集合是 Si,那么有 Si+1Si{i+1}

考虑由 Si1 构造 Si,我们枚举 xSi1,那么只需要考虑它和 Si 中最后一个元素 y,新增出来的这一位之间的大小关系,即比较两个字符的大小。这样可以确定保留 x 或者 y

然后再集合中新增 i 即可。

考虑如何计算前缀 i 时的答案,那么从前向后枚举每一个选出来的后缀,维护前面选出的最优解是 x,当前枚举到的解是 y,那么显然有 |s[x:i]|>|s[y:i]|,并且 s[y:i]s[x:i] 的前缀。那么我们只需要比较剩下的部分,也就是比较 s[x+iy+1:]s[1:n] 的大小关系即可,这个可以扩展 KMP 预处理。

因此复杂度 O(nlogn)

.

5

[CF547E] Mike and Friends

考虑类比两个串的做法,先建立广义前缀树,那么一次询问相当于是问某个子树内,线段树上一个区间里面所有出现次数的和。

乍一看这是个二维的东西,考虑有一维是没用的,能不能减少一维。

这样定义线段树:u 节点的线段树区间 [i,i] 表示 u 节点的所有子串在 i 这个串里的出现次数。

那么依然可以线段树合并来更新,然后就没了,但是空间怎么算都不够用。

有一个利用 fail 树性质的做法:

先对所有串建立 AC 自动机,维护出每个串的接受状态。考虑将答案差分,变成询问在一个前缀内,某个串在其它串中的出现次数,那么只需要用 AC 自动机顺序读入每个串,将节点上的贡献 +1。那么 r=i 的询问的答案,就是 sk 接受状态的那个子树权值的和,直接 BIT 维护即可。

时间复杂度 O(nlogn),空间复杂度 O(n|Σ|)

考虑这个题的启发是:

那么:

[SRM550, R1 div1] Conversion Machine

考虑先把 S 最小步数变成 T,那么对于第 i 位,走过的步数一定是 ai+3bi 的形式。

考虑剩下部分走的总步数,设为 t,那么关系是 step[i]+tΣlim,从而可以解出 t 的上界 X

设剩下部分还要走 i 步的答案是 fi,那么答案就是 i=0Xfi,其中有 fn=n![xn]iFi(x)

考虑一个抽象的问题模型:

m 种颜色涂长为 n 的序列,记有 ki 个格子涂上了第 i 种颜色,则需要满足 i[1,m],kiai(mod3),问有多少种不同的序列。两个序列不同,当且仅当某个位置涂上的颜色不同。

m11,n109,0ai<3

考虑对每种颜色构造 EGF,即 Gn(x)=i[imod3=an]xii!,那么答案是 n![xn]iGi(x)

考虑单位根反演,那么 Gn(x)=i13k=02ω3k(ian)xii!=13k=02ω3kaneω3kx

那么答案就是 [xn]n!3ni(ex+ω3aieω3x+ω32aieω32x)

可以 3n 暴力展开 product,那么答案累加 ABn3n,其中 A 是多项式前面的系数乘积,B 是指数上 x 的系数和。

注意到 ω3=ei2π3=3i12,令 i2=3 扩域计算即可。

.

6

[NOIAC D1 A] 异或

证明:

首先有取等的条件是 trivial 的,对于 a<b<c 的情况,首先对高位考虑。

如果 a,b,c 的最高位均相同,可以规约到去掉最高位时的情况;

如果 a,b,c 的最高位均不相同,那么结论直接成立;

如果 a,b 的最高位相同且与 c 不同,那么结论直接成立;

如果 b,c 的最高位相同且与 a 不同,那么结论直接成立。

那么判断一个集合合法,只需要将其排序即可。

p 是满足 2ix 的最小的 i,将 a[] 去除低 p 位后分类,那么不同组之间显然是随便选,同一组内选择的数,必须满足第 p 位互不相同。

那么一个组里面只能不选,选一个或者选两个,算出每组的方案数相乘即可。

选两个的时候,相当于求有多少数,和一个数异或 x,直接 Tire 维护即可。

特殊情况是 x=0,特判即可。

.

7

[NOIAC D2 A] 矩阵填数

一个 n×m 的网格,每个位置需要填 [1,m] 的数字。给定 q 条限制 [(x1,y1),(x2,y2),v] 表示从 (x1,y1)(x2,y2) 的最大值必须是 v,求有多少种方案。

考虑如果限制矩形均不相交,那么答案很容易计算。

考虑如果两个 v 不相等的矩形相交了,那么显然 v 小的那个会控制相交的区域。但是如果 v 相等呢?这就比较难处理。

先只考虑 v 互不相同的情况,那么显然将矩形排序,然后枚举一个矩形,就只需要算出在它前面的的矩形,与它的交覆盖的总面积,这部分是由这个矩形控制的。

如果只有一种 v 呢。考虑枚举一个集合 S,然后算 S 个矩形均不满足限制的方案数容斥,这个很容易计算。

考虑把这两种做法合并起来,那么考虑先算出这种 v,去除之前的矩形的并,覆盖的总面积,这就是全集,然后枚举一个集合容斥计算全集的合法方案数即可,最后答案就是所有 v 乘起来。

考虑难求出的东西是一个集合覆盖的总面积 cu[S],显然 cu[S]=TS(1)|T|1ca[T],那么直接高维前缀和计算即可。

复杂度 O(n2n)

Manacher 复习

Manacher 和扩展 KMP 算法有着异曲同工之妙,都是维护一些特殊结构,然后达到均摊 O(n) 的复杂度。

Manacher 用于求出字符串某个位置的回文半径,定义为 l2,其中 l 表示以该位置为回文中心的串的最长长度。

对于偶数串 s 的回文中心,我们认为它在 |s|2 这个位置。

Manacher 维护一个当前找到的右边界最靠右的回文子串 [l0,r0],那么可以发现 r[i]minp+r[p]i,r[2pi],其中 [pr[p],p+r[p]] 是当前维护的回文子串。可以证明这样做的复杂度是 O(n)

扩展 KMP 用于求出一个串 s 和它的每一个后缀 s[i:] 的 LCP z[i]

维护当前找到的右端点最靠右的一段 Border [l,r],那么如果 ir,可以发现 z[i]minz[il+1],ri+1。可以证明这样做的复杂度是 O(n)

最长回文前后缀这种东西还是回文树吧...

.

8

[CF573E] Bear and Bowling

O(n!) 爆搜的常见优化是 O(2n) 状压,O(2n) 爆搜的常见优化是 O(n2)/O(poly n) DP,这个要记清楚了。

那么考虑一个 naive 的 DP:设 f[i,j] 表示考虑前 i 位,选了 j 个,可以发现这个状态是容易转移的。

f[j] 表示选 j 个数的最优答案,考虑加入一个 i,更新到的一定是一段后缀。直接数据结构维护就好了。

[HDU3306] Another Kind of Fibonacci

考虑 fn2=(Afn1+Bfn2)2=A2fn12+B2fn22+2ABfn1fn2

fnfn1=(Afn1+Bfn2)fn1=Afn12+Bfn2fn1

这样就可以维护了。也就是说维护乘积求和的时候要试图找乘积的递推关系。

维护 |snfn2fn12fnfn1|,转移矩阵是 |1000A2A21AB2B2002AB2AB0B|

特征方程复习

对于一阶递推 xn=pxn1+q,尝试构造等差数列:

d 满足 xnd=p(xn1d),推得 xn=pxn1+(1p)d,也就是 (1p)d=q,d=q1p

那么 {x}d 是等比数列,xn=pnx0,其中 x0=x0d,xn=xnd

对于 xn=axn1+bxn2,用 xnxn,得到方程 xn=axn1+bxn2,化简得到 x2axb=0

设它的两个特征根是 X0,X1,那么存在系数 A,B,使得:

xn=AX0n+BX1n

使用前两项解出系数即可。

[HDU2256] Problem of Precision

首先求 (2+3)2nmod1024 就直接做,但是现在要求 (2+3)2nmod1024

(2+3)2n=(5+26)n

我们知道 (5+26)n+(526)n=2Re[(5+26)n]

(526)=0.101... 是个小于 1 的数字。

那么 (5+26)n=2Re[(5+26)n]eps,其中 0<eps<1

那么答案就是 2Re[(5+26)n]1,扩域即可。

树状数组上倍增

树状数组的 d[i] 维护的是 [ilowbit(i)+1,i] 这一段区间的和,如果我要问 [i+1,i+2k] 这段区间的和,就对应到 d[i+2k],前提是 ki 的 lowbit,我们发现倍增过程恰好满足这个性质。

[联合省选2020 A] 冰火战士

考虑先把两个数组都升序排序,以下做法基于该结论讨论:

找到最后一个满足 si(i)sf(i) 的温度 i,和第一个满足 si(j)>sf(j) 的温度 j,答案出自 i,j 中的一个。

考虑如果倍增一个温度 T,需要对 ai 求前缀和,对 af 求后缀和,这不太好办。那么做差值,把 af 取反,温度 1,用当前的总和减掉前缀和即可。

BIT 上倍增即可 O(nlogn)

灵光一现

求两个字符串 S,T 内共出现了多少个本质不同的子串。

基环树的 Prufer 序列构造

每次找到编号最小的一个叶子,把它的父亲加入序列。如果它的父亲在环上,那么不删除;否则删除这个父亲。

那么可以发现,树上点 u 在序列中出现次数是 du1,环上点 u 在序列中出现次数是 du2,并且序列中最后一个点一定是环上的点,并且序列的长度 = 点数 - 环长。

如果这个时候已经确定了环的形态,那么就可以确定这个基环树。这里的形态指的是有哪些点,以及点的顺序。

注意一个大环没办法用这种构造表出,或者说表出的结果是空序列 + 大环。

[Code FEST 2017 R3 J] Unicyclic Graph Counting

给定 n 个点各自的度数 d1...dn,求有多少个满足该度数序列的有标号基环树。

直接 DP 对推广的 Prufer 序列计数,维护 1(dik)!,k=1/2,即可 O(n2)

注意 n 个点的有标号环有 (n1)!2 种形态。

毒瘤

n 个点的有标号树有 nn1 种形态,那么 n 个点的有标号基环树有多少种形态?

树是简单图,因此不能有自环或者重边。

先枚举一个环长,构造上面的序列,有:(n1)!2+12l=3n1nlnnl1

OEIS-A057500

.

9

同余最短路

你一开始在 0 处,每次可以走 ai,i[1,n] 步,求你在 [0,m] 中能到达多少不同的点。m 很大,但是 minai 很小。

b=minai,那么每个 ai 都可以被表示成 kib+ri 的形式,其中 ki1,0ri<b

d[i]=x 表示满足 xmodb=i 的,最小能到达的点 x。那么形如 d[i]+pb 的点都可以到达,如果能对每个 i[0,b) 求出 d[i],我们就能解出问题的答案。

考虑对每个 aij[0,b),连边 (j,(j+ai)modb,ai),那么 d[i] 等价于在这张点数 O(b),边数 O(bn) 的图上从 0i 的最短路,使用 Dijkstra 求解即可。

[WC2016] 论战捆竹竿

显然等价于一个模型:一开始在 0,每次可以走 ai 步,问 [0,wn] 中可以到达多少点。这里 ai=n|Border[i]|

显然 minaiO(n) 级别的,那么直接建图是 O(n2) 的,这样有 50pts。

不会了/kk

reflect

线段树合并的时候,判断要这样写:

不要用乘积!!乘积会溢出,很可能被对着卡!!

[THUSCH2017] 大魔法师

先把信息写成向量的形式,然后通过矩阵来进行变换。

|AiBiCi|

考虑 1 操作,相当于乘上 |100110001|

考虑 2 操作,相当于乘上 |100010011|

考虑 3 操作,相当于乘上 |101010001|

考虑 4 操作,相当于加上 |v00|

考虑 5 操作,相当于乘上 |1000v0001|

考虑 6 操作,相当于先乘 |100010000| 再加 |00v|

矩阵的运算满足结合律和分配律,因此维护乘法和加法标记即可。

具体来讲,维护当前区间的值是 d[k]m[k]+r[k],区间整体加的时候直接加在外面,区间整体乘的时候两边都要乘。注意永远都是右乘。

循环展开,然后做乘法 a×b 的时候特判掉 a[i][j]=0 的情况,也就直接 continue,常数会小很多。卡到了 loj 第三页,我不行。

当构造函数被调用很多次而可以特判取代时,不写构造也能减少常数。

.

10

[ZJOI2013] K大数查询

二分一个 mid,将询问划分成两类:答案 mid 和答案 >mid 进行分治。

考虑分类的过程, 我们只需要把 cmid 的修改,在 [l,r] 区间加一,那么对于一个询问,它的答案 mid 当且仅当 sum(l,r)c

注意线段树需要还原,复杂度 O(nlog2n)

[AGC001 E] BBQ Hard

考虑即是求 i=1nj=1i1(Ai+Aj+Bi+BjAi+Aj),显然它等于:

12[i=1nj=1n(Ai+Aj+Bi+BjAi+Aj)i=1n(2(Ai+Bi)2Ai)]

考虑求前面一个柿子,(Ai+Aj+Bi+BjAi+Aj) 等价于网格图上,从 (Ai,Bi) 走到 (Aj,Bj) 的方案数,每步只能向上或者向右走。

考虑对整体递推,就是把每个 (Ai,Bi) 处的 DP 值设为 1,然后向右和向上递推,在每个 (Ai,Bi) 处统计答案。

O(n+V2),其中 V 是值域。

Border 的四种求法

Periodicity Lemma 指出了周期之间是存在联系的,这个联系基于一个基本事实:周期的倍数依然是周期。

存在结论:

2kn 的时候,这个结论很好理解,因为这个时候串可以被表示成 AXA 的形式,其中 A 是 Border,X 可空。那么周期显然是 |AX|=|s||A|

2k>n 的时候,这个时候我们把串理解成 XA 的形态,其中 A 是 Border 并且满足 AXA 的前缀。显然有 |A|>|X|,那么 X 这一整个部分一定在后面的 A 中出现了,然后我们可以把 X 去掉,把 A 分解成 XA。由此不难发现 |X|=|XA||A| 是串的周期。

根据上面的推导,不难发现反过来也是成立的:

也就是说一个串的 Border 和一个串的周期是本质相同的集合,在表现上形成互补的关系。

[HDU3746] Cyclic Necklace

求整串的最短周期,相当于求串的最长 Border,直接 KMP 即可。

[WC2019 Lecture] 周期串查询

s[l:r] 是否可以被分解成 XkX 的形式,其中 k2XX 的可空前缀。不存在输出 1

即求最小周期,是下面这道题的弱化版。直接求出所有 runs,那么答案相当于一个矩形前缀求最小,直接离线二维数点即可。

[BJWC2018] Border 的四种求法

.

11

[Gym102978H] Harsh Comments

n 种 A 物品,权值 aim 种 B 物品,权值 bi。每次操作可以随机选择一个物品删除,概率是 aisbis,其中 s 是当前状态下剩余所有物品权值的和。求删光所有 A 物品的时间的期望。

n,m100,Ai100,Bi<998244353

考虑 min-max 容斥,那么就枚举一个子集 T,求这个子集的元素至少有一个被删掉的时间的期望。

可以把这个子集看成一个整体,设权值和是 v,那么期望是 iTaiai+v+iTbibi+v+1

方便起见权值记 pi,那么答案是 T(1)|T|1(iTpipi+si(T)+1)

=T(1)|T|1iTpipi+si(T)+T(1)|T|1

=1+T(1)|T|1iTpipi+si(T)

=1+i=1n+ms>0(1)s1pipi+s×[]

这里 [] 表示这种状态的系数和。有多少种方案能选出一个 A 的子集,使得不包含 i 且和是 s,求它们的系数和。

对 A 的前后缀做两遍背包,O(n2|V|)。枚举 i,s,p,通过前后缀拼出方案数,O(n3|V|2)

考虑先做出背包 f[]O(n2|V|)。然后消除 i 的影响,就是除掉 (1+xpi),直接模拟即可,O(n|V|)

总复杂度 O((n+m)n|V|),其中 Vai 的值域。

矩阵转置与转置原理

[bzoj3583] 杰杰的女性朋友

一张 n 个点的图,每个点有一个 k 维入度向量 Pi=|in[i,1]in[i,2]...in[i,k]|k 维出度向量 Qi=|ou[i,1]ou[i,2]...ou[i,k]|

对于任意两个点 i,jijQi·Pj 种走法。

q 次询问 u,v,d,表示从 uv 经过不超过 d 条边的路径有多少条。

q50,n1000,k20,d109

可以发现转移矩阵就是 QPT,我们要求 (QPT)d。但是 QPTn×n 的矩阵,这样显然不行。

长度恰好为 d 时的答案就是 u0(QPT)d=u0Q(PTQ)d1PT,中间那一部分就可以快速幂了。

答案就是 u0Q(i=0d1(PTQ)i)PT,设 D=PTQ,考虑中间那一部分怎么计算。

处理 i=0d1Di,考虑倍增预处理 Ai=D2i,Bi=j=12iDj,有 Bi=Bi1+Bi1Ai1=Bi1(Ai1+I)

然后对 d1 的每个二进制位分段,然后每一段就是一个 B 乘上一个 A 的形式。

.

12

训练 31 订正

B.

考虑直接点分治,然后维护前缀李超树,时间复杂度 O(nlog3n),空间复杂度 O(nlogn),常数大的一匹,没过去。

考虑如果是序列问题,就直接 n 分块,一个询问被拆成至多 n 个整块询问,由于李超树查询是一个 log,所以复杂度 O(qnlogn)

考虑先把询问按照重链剖分的 dfs 序划分成 logn 段,那么现在有至多 qlogn 个询问,搞成 qnlogn 个整段查询,然后复杂度 O(nlog2n+qnlog2n),看起来都不如直接点分治,但是感觉会松一些。

考虑把 qlogn 个区间对应在线段树,然后对线段树的每个节点建李超树,这部分复杂度 O(nlog3n),然后 qlog2n 次询问查询的复杂度就是 O(nlog3n+qlog3n),常数比点分治小很多。空间 O(nlog|V|)

李超树两个 log 注意别写满,第二个 log 很松,没用的线段直接 return 即可。

A.

考虑即相当于有一些点,一些只能往左走,一些只能往右走, 一些没有限制,求 1n 的方案数。

考虑一个非状压的 DP,设 f[i]表示考虑前 i 个点的状态,注意到只考虑前 i 个点路径可能未结束,也就这里面有很多段路径。再加一位同时维护路径的段数,设 f[i,j] 表示考虑前 i 个点,现在有 j 段路径未结束。因为路径没有结束,所以一段路径的末端一定是 R 点或者 B 点。

考虑当前 i,如果是 L,那么可以接在一段路径后面,也可以把当前路径连在起始段后面。如果是 R,那么可以新建一条路径,也可以接在一条路径前面。直接转移即可,复杂度 O(n2)

.

13

C.

考虑用 LCT 维护森林,然后两个子树合并的时候,现在的并集应该等于两个部分的大小加起来,然后减掉交集。

考虑这个交集,实际上就是上一次合并时这两两个连通块的并集,因为显然新加入的元素不可能有交。

于是直接拿 LCT 维护每棵树的答案,合并分裂都解决了,每次分裂的时候,在这条边上记录一下现在的并集大小即可。

复杂度 O(nlogn)

.

15

[雅礼集训 2017 Day1] 字符串

考虑直接每次询问单独做,然后对 s,w 建立广义 SAM,然后询问 a,b 可以直接枚举 [li,ri] 然后在前缀树上倍增找到对应点,直接累加答案,复杂度 O(q(n+|s|+mlogn)) 但是很松,估计可以过 50pts。

注意到 qk105,然后数据分治...

B. Replicate Replicate Rfplicbte

C. Longest Rivers

[CF 1276F] Asterisk Substrings

把需要统计的串划分成六类 ,,s,s1,s2,s1s2。然后显然 , 都是 1,并且这两类不可能算重。s 可以简单求出,并且不可能算重。剩下的只有 s1,s2,s1s2 三种情况,并且这三种情况里是可能算重的。

考虑所有前缀,最后一个字符替换成 ,能有多少本质不同的子串。由于最后一个字符相同,所以可以删掉,那么实际上就是所有小于串长的前缀有多少本质不同的子串。所有后缀也同理。这样算这一部分内部不会算重,也不会和 s1s2 的情况重复,因此只剩下 s1s2 这种情况。

考虑对于 endpos 相同的 s1,可以选择的 s2 是均相同的,也就是需要计算一些后缀组成的集合的本质不同前缀数量。后者显然等于这些后缀的长度和减掉排序后相邻串的 LCP。

考虑 set 启发式合并,就是 O(nlog2n),这样需要同时建立前缀树和后缀数组结构。

一些后缀的本质不同前缀数量,等于这些后缀在后缀树上对应节点到根的链长并。实际上可以直接求 dfs 序,然后按照这个启发式合并。

梳理一下做法,先同时建立前缀树和后缀树,然后先算前面五个部分的答案。搞出后缀树的 dfs 序和欧拉序,然后处理出 O(1) LCA。定义后缀结构体,维护这个结构体的 set,然后按 dfs 序倒序遍历前缀树,维护 endpos 整体 +2 的集合和它的权(set),然后启发式合并,每次合并相当于取消掉原来两个的贡献,加入新加入的两部分贡献。

O(nlog2n)

最小回文划分

只需要考虑对最长回文后缀应用 WPL 即可。

di[x]=len[x]len[nxt[x]],设一段等差数列的末端是最长的一个 nxt[x] 满足 di[x]di[nxt[x]],记一段等差数列的 slink[u] 均指向上一段等差数列的末端。

考虑设 g[x] 表示 x 所在的等差数列中,比 x 段的回文串对应的转移位置的 f[] 值的并集。当一个回文后缀再次出现时,g[x] 需要被重新更新,这时它的准确值是 g[nxt[x]] 加上新加入的一个元素,是 f[ilen[lk[x]]di[x]]

只需要用 g[] 去更新 f[i] 即可。复杂度 O(nlogn)

注意这里 nxt[x] 一定会在 x 之前被更新掉,因为它是 x 的 Border!!

OI-Wiki

UVA11584

[CF 932G] Palindrome Partition

如果 A=B,那么把 Br 穿插到 A 中间得到串 C,串 C 必然是回文串。例如:

考虑 skr 穿插 s1sk1r 穿插 s2......可以发现这等价于拿 sr[|s|/2+1:] 穿插 s[:|s|/2],然后就会得到一个新的串 s,每对 ts 中双射一个偶回文子串。

那么相当于求 s 的偶回文划分数量,这个只需要钦点每个状态都只出现偶回文串即可。

O(nlogn)

[CF 906E] Reverses

考虑一个 naive 的 DP,设 f[i] 表示考虑前 i 个位置的答案,那么显然有 f[i]=f[i1](s[i]=t[i])f[i]=minjf[j]+1。显然 j 应该满足 s[j:i]=tr[ni+1:nj+1]

由于 DP 数组有单调性(错的!),所以求最小的 j。把 t 反过来,相当于从 s[i] 向前从 t[ni+1] 向后求一个反向 Border,显然它的本质和区间 Border 相同,然而区间 Border 是众所周知的不可做问题。

考虑两个对应位置的子串反转其中一个会相等,就等价于两个子串插起来之后得到的是一个偶回文串。

求最小偶回文划分即可。O(nlogn)

.

16

[CF590E] Birthday

一眼秒了。

先建出 fail 树,显然一个串的子串是它在 fail 树上的祖先。我们希望不存在偏序关系,等价于求 fail 树的最长反链,也就是传递闭包后的最小链覆盖。

就左边建一排点,右边建一排点,每个点向源 / 汇的流量都是 1,然后右点向左点连 边,然后答案是点数 - 最大流。

求方案?

考虑求出拆点二分图的最大独立集,具体操作是:

从每个没有匹配的左部点开始 dfs,左->右的边只走没有匹配的边,右->左的边只走匹配的边,然后所有 dfs 到的左部点和未 dfs 到的右部点就组成了最大独立集,左右都在最大独立集里的点 i 就在最长反链里。

[CF700E] Cool Slogans

前缀树上的最长链?有一个问题是,转移时应不应当加一。

如果父节点在子节点中出现了两次以上的话,就应该加一。否则可以把父节点替换成这个点,然后不加一。

线段树合并即可。

坑点:转移的时候需要维护出现在这个节点实际上是哪个点,因为可能不选择这个节点。

坑点:必须从树根往下 DP,因为倒过来的过程可能有多种不同的选择,但是从上向下只有一种选择。

[HDU5390] Tree

可持久化 Tire 的带修只能类似于线性基带修那样,线段树分治来解决。

一个序列带修可持久化 Tire 的在线想法:按序列位置线段树分治,然后一个元素持续存在的位置是一段前缀,它会被拆分成 log 个可行段。于是我们总共有了 O(nlogn) 个元素,我们对线段树的每个节点建立 Trie,这样时空复杂度都是 O(nlog2n)

或者换句话说,对集合(强调无序性)建立的可持久化结构,有一个通用的带修方法。因为本质上这类问题相当于“给一些元素,每个元素在 [li,ri] 这一段位置内有效,维护每个区间对应集合的 DS”。

这个问题有一个通用解决办法就是,把一个元素在线段树上划分成 log 段区间,然后由于查询是单点查询,所以标记永久化,在线段树的每个节点上,维护对应集合的 DS。

这样做的空间复杂度是 O(nlognE(n)),时间复杂度是 O(nlognΩ(n)),其中 E(n) 是该 DS 一次操作的空间复杂度,Ω(n) 是该 DS 一次操作的时间复杂度。

通常理解的线段树分治相当于对时间轴可持久化,本质上还是解决上面的模型。

实际上是两种角度!!一种角度是用 BIT 那样的单层结构实现可持久化结构,另一种角度是用线段树或分块那样的多层结构实现可持久化结构。

本质上分块是三层线段树!!

考虑原问题,首先想到可以树上可持久化 Tire,但是没有树上 BIT 所以无法支持修改,这样不行。

因为所有查询路径都是从根出发的,这种情况下用不着树链剖分!!树链剖分解决的是任意两个特殊点之间,路径查询的问题。如果一个端点固定,可以被 dfs 序完美代替,因为这个时候另一个点的影响区间在 dfs 序上一定是连续的!!

考虑拿多层 DS 维护。一个元素的影响范畴是它的子树。对 dfs 序建立线段树,然后线段树上每个节点维护一个 Tire,就可以支持在线修改和查询,时空复杂度 O(nlognω),空间上过不去。

考虑可以对线段树上每个节点维护一个 set,里面存所有操作中覆盖到这个区间的元素,按出现时间排序。然后可以只维护一棵 Trie,对每个节点单独做一遍 RMQ,时间 O(nlognω),空间 O(n(logn+ω))

回文树的双端插入和后端删除

论文

双端插入:同时维护两个指针 pre,suf,分别指向当前串的最长回文前缀和最长回文后缀。注意到一个串的最长回文前缀同时也是它的最长回文后缀,因此从 pre/suf 开始跳 nxt[] 即可。

[HDU5421] Victor and String

从前后段插入字符,询问本质不同的回文串数量和所有回文串数量。

本质不同回文串的数量是回文树的节点数。所有回文串的数量是 endpos 集合大小之和,这个考虑贡献,每新建一个字符直接求祖孙链和即可。

一种不基于势能分析的插入算法:维护一个转移数组 fail[u,c] 表示在 u 点后面扩展一个字符 c,转移到的那个点 v,其中 v 代表的串是最长的 u 的回文后缀,满足 v 的前驱字符是 c

考虑更新 fail[u] 数组,显然 fail[u] 是在 fail[nxt[u]] 的基础上进行了 O(1) 级别的更新。设 nxt[u] 的前驱字符是 x,唯一的更新是 fail[u,x]=nxt[u]

注意如果 u 的前驱恰好是 c,那么实际上要找的点就是 c

这样时空复杂度都是 O(n|Σ|),可以通过可持久化数据结构优化到 O(nlog|Σ|)

在 Trie 上建立回文树 / 末端删除:可以发现后者完全是前者的子问题,而前者可以通过上面的算法简单实现。

当然了 lst[] 指针也必须可持久化才行。

类似的处理办法还出现在了 KMP 自动机中。本质上这的确是一类自动机,只不过没有起始状态和接受状态。

[HDU5394] Trie in Tina Town

就是上面的模板。

.

17

[LOJ517] 计算几何瞎暴力

考虑一次排序之后,下一次排序之前,这个数组每时每刻都可以被划分成两个部分:前面一部分是有一定顺序的,后面一部分则按照加入顺序排列。

考虑这一段之间内,前面那一部分,一定是先是升序的,然后某次 4 操作之后,变成了无序的。但是不考虑这次 4 操作,依然是升序的。如果我们给 4 操作打一个 lazy tag,那么这部分就是升序的。

考虑分开维护,前面一部分拿一个 Trie 维护,询问相当于求前 k 大之和;后面一部分拆开位拿数组维护,询问相当于求前缀和。

1 操作,直接接在后面那部分。

2 操作,前后分开询问。后面的前缀和是正确的,前面的需要对 Trie 上每个节点维护 ω 个信息,表示这个子树每一位上有多少 1。

3 操作,后面的前缀和拆位更新,然后整体打一个异或 tag x,表示现在每个数是 aix

4 操作,把 Trie 树的整体 tag ttx,然后把数组里面的数字都加入 Trie。

复杂度 O(nω2)

[CF963D] Frequency of String

考虑长度不同的串只有 O(L) 种,对于同一种长度,只可能有 O(|s|)endpos

于是就 set 启发式合并然后直接做了。

[CF587F] Duff is Mad

先建 fail 树。考虑一个串的所有出现位置是它在 fail 树中的子树。

把询问差分:问 s1...srsk 中出现了多少次。

考虑从 1n 枚举 si,然后给 si 的所有出现位置 +1,就相当于子树 +1。然后查询一个 k,就相当于对 AC 自动机上的一条路径求和。

考虑按串长分块,考虑串长 n 的串直接暴力求出这条路径,串长 n 的串只有 n 个,对 fail 树上每个点额外维护一个 cnt[] 表示这个子树里面,第 j 种长串有多少个。长串的答案我们直接单独维护,每次子树加,枚举长串直接答案加权即可。

O(nn)

[NEERC2015] Distance on Triangulation

考虑对于三角剖分的一条边,它左边部分的点集是 L,右边部分的点集是 R,两个端点是 p1,p2,则所有 L,R 之间的路径一定且恰好经过 p1,p2 中的一个。

然后我们就可以找一条边使得左右两边分的尽量均匀,然后从这两个点开始广搜,然后分治下去计算。

形式化的理解,相当于在维诺图(对偶图?)上边分治,因为这里维诺图一定是一棵树,可以简单证明。

考虑怎样建立维诺图,就只需要找度数为 2 的点,然后把这个点删掉,然后给这个区域新建一个点,然后把新点挂在对边上。

每删掉一条边的时候,把当前的点个边上的点连起来。

slstxdy

给定一个点 O 和二维平面上的若干点构成的集合 S,求有多少种方案可以选出一个 SS,使得 S 中任意三个元素构成的三角形不包含 O

数据保证任意三个点不共线。

不会做/kk

.

18

组合数系:任意一个正整数 n 可以被表示成 n=(a1)+(b2)+(c3)

[LOJ6055] 一道数学题

首先解递推式,得到通项是 f(n)=nk+i=1n1ik2n1i。后面是一个比较畸形的自然数幂和问题,应该不是一个关于 ik 次多项式。

=2n1j=0k{kj}j!i=1n1(ij)2i=2n1j=0k{kj}j!Sj(n)

错位相减:Sk(n)1/2Sk(n) 尝试求出 Sk(n)Sk1(n) 的关系。好思路!!

有时候错位相减会减不出东西来,但是碰上没有求和方法的柿子要往这方面想!!

如果求和式中包含组合数,那么错位相减大概率可以成功。如果求和式中包含指标的定次幂,那么应该先展开一下搞出组合数。

S0(n)=12(n1),Sk(n)=(1k)(nk)2(n1)+Sk1(n)

这样所有的 Sj(n) 可以在 O(k) 时间内推出,只需要 O(k2) 处理出第二类斯特林数,就有 O(k2) 的 60pts.

考虑一行第二类斯特林数可以直接拿通项公式卷积,这样就是大常数 O(klogk),可以通过原题非加强版。

关于错位相减的总结:

(11a)Tk(n)=(n+1k)anTk1(n)

Dk(n)=j=0k{kj}nj2nj

Yk(n)=j=0k{kj}j!Tj(n)

{nm}=i=0m(1)ii!(mi)n(mi)!,构造 ai=(1)ii!,bi=iki!,然后直接卷积即可。

朴素做应该可以 O(nlogn),好像可以通过插值做到 O(n)

i=0n(ik)ik:常幂展开之后,需要对所有 j 求出 i=0n(ik)(ij)​,这个柿子真的能做吗.../kk

插值!i=0n(im)ik 是一个 m+k+1 次多项式!

[LOJ6608] 无意识的石子堆

n×m(nm) 的棋盘,有 2n 个棋子,求有多少种放棋子的方案,使得每个行每列都只有不超过两颗棋子。

考虑先确定列的分配,再确定行的分配。枚举 i 列放了两个,那么有 2(ni) 列放了一个。

答案是 i(mi)(mi2(ni))s[i],其中 s[i] 表示已知 i 列放了两个的情况下,有多少种合法的行分配方式。

s[i]:有 2n 个小球,共 n 种颜色,有 2ni 个不同的盒子,其中 i 个盒子需要放两个小球,2n2i 个盒子需要放一个小球。同一个盒子里面的小球必须异色,求放置方案数。

首先只需要强制所有盒子都不为空,然后插板,就能满足接近所有限制。唯一不满足的限制是一个盒子里面的小球必须异色。

根据二项式反演,恰没有盒子使得小球同色的方案数等于钦点 j 个盒子里的小球同色,然后容斥,系数都是 1

那么这里就是 s[i]=12n·2ij=0i(1)j(ij)(nj)j!2j×(2(ni))!

卷积即可,这样就是 O(nlogn),只需要一次卷积,不过常数还是不小。

[LOJ6289] 花朵

考虑直接有多大力就多大力 DP,复杂度 O(nm),可以拿到 37pts.

考虑如果是一个菊花,只有两种可能:选根,其它的全不选;不选根,其它的随便选。然后分治 FFT 一下,总共 52pts。

考虑如果没有摘掉的节点不相邻这个限制的话,相当于一个广义背包,可以直接分治 FFT 解决掉。

相邻不选的 DP 方程也可以写成卷积!这样来做,设 Au(x) 表示不选 u 对应的多项式,Bu(x) 表示选 u 对应的多项式,那么 Au(x)=v[Av(x)+Bv(x)],同时有 Bu(x)=vuxvAv(x)

答案就是 [xm](A1(x)+B1(x))

那么一条链也做完了,这样有 67pts.

生成函数的乘法是可以交换的,考虑链分治,把树剖成若干链,然后按照 dfs 序的倒序处理每一条链。先遍历一遍,把链上每个点在这个时候真实的多项式求出来,然后对整条链带权分治 FFT。

考虑这样做什么时候会有优化作用:每次处理一条链的时候,每个节点的多项式大小尽量均匀。容易发现多项式大小和子树大小是相关的,因此选用重链剖分,这样会使得每个点在乘到根的过程中,只出现在 O(logn) 个多项式中。结合一次分治的复杂度,总复杂度 O(nlog3n)

[AGC005F] Many Easy Probs

考虑 i 个点的最小联通子树的大小和,可以算每个点的贡献。考虑一种选取方案里面,一个点有 1 的贡献,当且仅当有两个点之间的路径会经过这个点。

考虑所有点对路径都不经过这个点,等价于只能在挖掉这个点之后的若干联通块里面选择。于是贡献和是 (ni)t(sz[t]i),这里上方子树我们也认为是一个子树。

ans[i]=j=1n[(ni)k:j(sz[k]i)]

考虑对 sz[] 分类,得到:

ans[i]=n(ni)k=1ncnt[k](ki)

这里直接把 cnt[n]n

ans[i]=k=1ncnt[k](ki)=1i!k=1ncnt[k]k!(ki)!

这样就直接卷积。

.

19

[LG P5824] 十二重计数法

n 个球放到 m 个盒子里。

  1. 球之间互不相同,盒子之间互不相同:mn
  2. 球之间互不相同,盒子之间互不相同,每个盒子至多装一个球:n!(mn)
  3. 球之间互不相同,盒子之间互不相同,每个盒子至少装一个球:m!{nm}
  4. 球之间互不相同,盒子全部相同:(n+m1m1)
  5. 球之间互不相同,盒子全部相同,每个盒子至多装一个球:[nm]
  6. 球之间互不相同,盒子全部相同,每个盒子至少装一个球:(n1m1)
  7. 球全部相同,盒子之间互不相同:[xn]1(1x)m
  8. 球全部相同,盒子之间互不相同,每个盒子至多装一个球:[xn](1+x)m
  9. 球全部相同,盒子之间互不相同,每个盒子至少装一个球:[xn]x(1x)m
  10. 球全部相同,盒子全部相同:整数拆分,等价于背包,多项式 exp
  11. 球全部相同,盒子全部相同,每个盒子至多装一个球:[nm]
  12. 球全部相同,盒子全部相同,每个盒子至少装一个球:去掉 m 个球,和 10 等价

[CF1096G] Lucky Tickets

首先题目就是让我们求的就是 k 项式系数第 n/2 行的平方和,即对所有满足 0din/2di=n/2,长度为 k 的序列 di,求 (n/2)!2(d1!d2!...dk!)2 的和。

构造 A(x)=i=0n/2xii!2,答案即是 (n/2)!2[xn/2]Ak(x),随便怎么搞搞就行,复杂度 O(nlognlogk) 或者 O(nklogn)

好像不是很能这样转化....因为有时候,两个系数带权乘起来加起来可能是相等的。或者换句话说,有 k 个系数非零项的多项式的 n 次幂不一定恰好有 k+n1 项。

那就按照朴素的思路来,构造 A(x)=tSxt,那么答案是 An/2(x) 的各项系数的平方和。

求幂:设 B(x)=Am(x),两边对 x 求导,其中 Am(x)dx=[Am(x)]A(x)=mAm1(x)A(x)

也就是 B(x)=mAm1(x)A(x),也就是 B(x)A(x)=mA(x)B(x)

A(x)=i0aixi,B(x)=i0bixi

A(x)=i0(i+1)ai+1xi,B(x)=i0(i+1)bi+1xi

比较系数得 j=0i(j+1)bj+1aij=j=0im(j+1)aj+1bij,把 bi+1 那一项连同系数提出来就可以 O(nk2) 递推出每一项系数了。

b0=a0m,bn=1na0[mj=0n1(j+1)aj+1bn1jj=1naj(nj+1)bnj+1]

有效的 bi 一共有 nk 项,而 a 的有效项只有 k 个,因此复杂度 O(nk2)

[PKUWC2018] 猎人杀

对于一个整体,它出现在 1 之前或之后的概率与其它元素是毫无关系的,只跟这个整体的权值和和 1 的权值有关。

考虑算“某个集合里的所有元素均在 1 之前出现”的概率并不好算,因为分母每时每刻都是在变的,这时候我们不能把这些元素当做一个整体。

但是反过来,算某个整体均出现在 1 之后的概率十分好算,这个时候答案实际上就是 w1sum+w1,其中 sum 表示这个整体的权值和。

于是我们考虑容斥,钦点一个点集 S 个的人在 1 之后被选到,答案应当是:

S(1)|S|w1sum(S)+w1

这样可以像二项式反演那样按照集合大小分类,也就是设 f[i,j] 表示选 i 个数和是 j 的方案数,答案是 i=0n1(1)ijf[i,j]w1j+w1,背包一下就是 O(n|V|),有 50pts。

然后想到可以直接按照集合的和来分类,设 f[j] 表示和为 j 的所有集合的容斥系数和,答案是 jf[j]w1j+w1

剩下的问题是处理 f[j],这里每次往 j 里面添加一个元素,我们都要把系数乘上 1,因此有 f[j]=[xj]i=2n(1xwi)

这个可以按照区间内 wi 的和带权分治,复杂度 O(|V|log2|V|)

枚举子集容斥的容斥系数和是可以背包,并且可以写出生成函数的!!这一点一定要记清楚。

[XXI Opencup GP of Tokyo H] Harsh Comments

n 个 A 物品,权值 aim 个 B 物品,权值 bi。每次你会以 ai/bis 的概率选择一个 A / B 物品把它扔掉,其中 s 是剩余所有物品的权值和。求你把所有 A 物品扔光的期望操作次数。

考虑 min-max 容斥,相当于对所有 A 物品的集合 S,求集合 S 中有任意一个物品被删掉的期望时间,容斥系数是 |S|1

这个时候物品分两类,一类在集合 S 内,一类在集合 S 外。S 内的元素可以看成整体,实际上可以考虑贡献,答案就是 xSvxvx+sum(S)

答案是 S(1)|S|1xSvxvx+sum(S)

首先 sum(S) 不大,可以按照 sum(S) 分类。如果先枚举 x,柿子变成 xS(1)|S|1vxvx+sum(S)

处理出不包含 x 的背包 f[],那么实际上一个 x 的求和就是 jf[j]vxj+vx,这里的 f[j] 是所有和为 j 的集合的容斥系数和。

这个可以背包,考虑新加入一个元素,所有集合的系数同时乘 1,也就是 f[j+vi]f[j]

相当于乘上一个生成函数 (1xvi),因此是可逆的,每次枚举 x 的时候模拟除法即可。

复杂度 O(n2|VA|)

.

20

[CF755G] PolandBall and Many Other Balls

白给好题

n 个球,可以选连续的两个作为一组,也可以选一个作为一组,求对每个 i[1,k],分 i 组的方案数。

考虑先选出连续两个的放置方案,相当于求 n1 个位置,放 j 可互不相邻元素的方案数。这个可以容斥然后卷积计算就是 O(nlogn)

然后再选出连续一个的放置方案,发现没法卷积...

考虑对于 i,答案实际上很好确定。枚举 j 个位置放了两个,然后先保留最后 j 个位置不选择,然后从前面的 nj 个位置选出 i 个,然后再从 i 个位置里面选出 j 个把它变成两个,后面选择的位置顺次向后推移,可以发现这和原问题等价。

ans[i]=j(nji)(ij)=j(nj)!(nji)!j!(ij)

发现还是没法卷积...

考虑 j(nji)(ij) 的组合意义还有一种解释:先从前 i 个里面选任意个,然再从剩下的里面选 i 个,需要不会选重。

可以钦点前面有 j 个选重了,得到另一种表示:

ans[i]=j(1)j(ij)(njij)2ij

n 很大的时候阶乘没法表示,不需要分段打表!因为 j 很小,除掉一个 n! 就可以做了,记住这个技巧!!

ans[i]=i!nij(1)jj!nj×2ij[(ij)!]2

处理下降幂即可,一次卷积 O(nlogn)

D5 A

定义积性函数 f(1)=1,f(pk)=pk+1,求 f 的前缀和。

考虑贡献法,实际上答案是 iiijn[(i,j)=1],然后就是莫比乌斯反演那一套...

.

21

D6 B

如果行列式的某行或者某列有公因子,可以把它提出来计算。

矩阵和它的转置的行列式相等。

考虑答案即是 det|(a1+11)...(a1+nn)(an+11)...(an+nn)|

提公因子得:

=12!...n!det|(a1+1)...(a1+1)n(an+1)...(an+1)n|

可以发现这里每行都是关于 ai+1j[1,n] 次多项式,且每行形式相同,因此可以通过变换把每行变成 (ai+1)j 的形式。

ai+1 因子,发现这个时候是一个每行的公比是 ai+1 的范德蒙德行列式,范德蒙的行列式有引理 detF=i<j(xjxi)=i<j(aj+1ai1),注意这里一定是大下标减掉小下标。

ans=(a1+1)...(an+1)2!..n!detF

考虑按照 ajai 的值分类,就对 aiai+maxai 分别做桶然后卷积。注意这样一对 i,j 会被算两遍,一遍正的一遍负的。因为我们知道结果总是正的,所以枚举一半即可。

D6 C

先考虑怎样选出一个 LIS 等于序列最大值 m 的序列。

记住上面两种方法!!选最前面的那个作为代表点,剩下的部分的方案数实际上可以表示出来!!

考虑枚举 m 的位置,设 f(n,m) 表示值域 [1,m],长度为 n,LIS 长度为 m 的序列有多少个,那么:

f(n,m)=i=mn(i1m1)mni(m1)im

可以发现这是一个对 n 的卷积,当然了这对原问题并没有帮助。

显然后面 mni 这一部分每个数字出现次数都是相等的,那么前面这一部分满足吗?

考虑所有情况下,每个数字不能出现的段长的和一定是相等的!这可以通过交换位置问题不变来理解。所以前面部分每个数字出现次数也是相等的。

换句话说,当 n,m 确定的时候,每个数字的出现次数相等且都是 nmf(n,m)

这样朴素做就是 O(n2)。但是 n5×104 依然不能做。不会/kk

.

22

[CF643G] Choosing Ads

区间严格众数有个简单做法:线段树每个节点维护一个二元组 (v,s) 表示当前区间的严格众数是 v,出现次数是 s。合并两个区间的时候,如果 vl=vr,那么 (vl,sl)·(vr,sr)=(vl,sl+sr),否则 (vl,sl)·(vr,sl)=(argmaxs,maxsmins)

k=100/q,维护 k 个二元组。合并的时候,先保留全部元素,按照出现次数排序,然后可以断言超出 k 的那些元素没用,维护差值即可。

注意区间众数和区间带修众数是一个莫队问题。

[ARC093D] Dark Horse

首先 1 放在哪里答案都是一样的,证明可以考虑 rotate,因此设 p1=1,然后答案需要乘 2n

考虑 n1 个集合 Gi={p2i1+1,...,p2i},实际上需要每个集合的最小值都不在 A={a1,...am} 中。

枚举一个 S{Gi},容斥计算钦点 S 中的每个 Gx 的最小值都在 A 中的方案数。

考虑能和 Ai 一起分到某个段的元素,是大于 Ai 的元素。如果把 Ai 倒过来,然后枚举每个 Ai 尝试把它分配到一个 Gx,这个时候已经选过的 >Ai 的数字个数只跟现在状态下 Gx 选取情况有关。因此可以倒着做状压 DP。

这样就是 O(nm2n)

[CF708E] Stu Camp

考虑一个状态数是 n3 的 DP:设 f[i,l,r] 表示考虑前 i 行,第 i 行的状态是 [l,r] 的概率。直接转移就是 O(n5) 的。

显然可以优化,设 pre[l]=pre[l1]+j=1lf[i,j,l],suf[r]=suf[r+1]+j=rmf[i,r,j]。处理这两个数组一共需要 O(n3) 的时间,然后转移就是 f[i+1,l,r]=(pre[m]pre[l1]suf[r+1])(kl1)pl1(1p)kl+1(kmr)pmr(1p)km+r

Al=(kl)pl(1p)kl,Br=(kmr)pmr(1p)km+r,这两个直接线性预处理,那么:

f[i+1,l,r]=(pre[m]pre[l1]suf[r+1])Al1Br

pre[l]=pre[l1]+Blj=1lAj1pre[m]Aj1pre[j1]Aj1suf[l+1]=pre[l1]+Bl(pre[m]Al1ssuf[l+1]Al1sCl)

suf[r]=suf[r+1]+Ar1j=rmBjpre[m]Bjpre[r1]Bjsuf[j+1]=suf[r+1]+Ar1(pre[m]Brspre[r1]BrsDr)

维护 pre,suf,pre,suf,A,B,As,Bs,C,D 即可。

复杂度 O(n2)

[雅礼集训 2018 Day4] Magic

考虑一个 naive 的 DP,设 f[i,j,k] 表示考虑了前 i 个位置,有 j 对相邻位置,最后一个的颜色是 k。朴素转移是 n4 的,稍微冷静一下就会发现本质上实际上 n3 的,然后 10 个点到手。

考虑每种颜色的卡的使用数量已经确定,那么给卡标号,这样每种颜色的卡可区分,最后答案除 iai!

f(k) 表示钦点 k 对相邻位置的方案数,然后二项式反演,答案是 g(k)=j=kn1(1)jk(jk)f(j)

考虑 n 个位置中有 k 对相邻,那么这个序列永远可以被划分成 nk 个排列。考虑将每种颜色 i,划分成 j 个排列的方案数组合起来,就可以得到将长度为 n 的序列划分成 nk 个同色排列段的方案数。

t[i,j] 表示将颜色 i 划分成 j 个排列有多少种方案,t[i,j]=ai!(ai1j1)/j!。设 Ai(x)t[i,j] 的 OGF,那么 f(k)=(nk)![xnk]iAi(x)

Ai(x) 带权分治 FFT 即可,复杂度 O(nlog2n)

.

23

[CF1349F2] Slime and Sequences

草,某题居然是原题

考虑枚举序列最大值 m,用最靠前的 LIS 双射序列,那么这个时候序列的数量就是 i=mn(i1m1)(m1)immni

考虑对于确定的 m,所有 [1,m] 的数字出现次数一定是相同的,因为后面 mni 这部分显然相同,前面部分一个数字在所有情况下能出现的段长和相同。

因此这个时候贡献是 nmi=mn(i1m1)(m1)immni,然后 O(n2),Easy Version 解决。

不一样!!比如 2 3 1 2 这样也是合法的。

考虑容斥,设 f(k) 表示钦点 k 个数字不合法的方案数,那么答案是 i=0n1(1)if(i)f(k) 怎么数啊....

考虑一个好序列 1 2 1 3 4 5 4,可以顺序写下每个数字出现的位置 (1, 3) (2) (4) (5,7) (6),我们发现题目限制等价于第 i 个括号的最大值大于第 i1 个括号的最小值。把每个括号降序排列,可以发现每个括号实际上是一个排列的极长下降子段。显然这是双射。

这样我们建立了从排列到好序列的双射,由此也不难知道好序列的总数一定是 n!

一个数字 x 的出现次数,就等于所有 n! 个排列中,第 x 段极长下降子段的长度和。先考虑长度为 n 的排列,有 k 个连续下降段的方案数怎么算。

显然有性质 nk=nnk1,且有递推式:

nk=(k+1)n1k+(nk)n1k1

也就是每个 < 的位置或者序列开头放置一个 n,上升个数不变;其他情况上升个数减一。

边界是 0n=nn=[n=0],n0=1

x 段极长下降子段等价于有 x1 个小于号。这种情况下重标号分配并不容易,如何求出第 x 段下降段的长度和?

可以考虑每个位置的贡献!枚举数字 m,它的答案是 i=1n(ni)im1(ni)!

这样处理欧拉数和计算答案都是 O(n2)

口胡证明是构造一个从排列到序列的映射,但是细节上出了点小问题。具体数学上好像有个代数证明。

考虑求一行欧拉数,设 f(k) 表示 n 的排列中钦点 k 个间隔是小于的方案数,那么:

nm=i=mn1(1)im(im)f(i)

f(k) 可以直接广义组合数分配标号搞出来,就是 f(k)=n![xn](ex1)nk。不会搞/kk

[LOJ6271] 生成树求和

考虑先拆位 O(log3c),然后对于这一位,需要计算所有“生成树边权在三进制下不进位加法和”在十进制下的和。

考虑由于是不进位加法,最后的结果一定是 0,1,2 中的一种。那么可以在边权上放一个 tu(x)=xcu,可以用矩阵树定理求出一个 A(x)=Tutu(x),我们关注的是 A(x)modx31 这个多项式。

设结果是 0,1,2 的分别有 cnt[0],cnt[1],cnt[2] 棵树,假设这是第 x(x0) 位,那么贡献就是 3x(0·cnt[0]+cnt[1]+2·cnt[2])

那么只考虑计算 cnt[1],cnt[2],可以发现不需要真的做循环卷积,直接将 ω3 代入多项式求值即可,也就是单位根反演:

i0[3|(ic)]ai=k=02ω3cki0aiω3ki

很可惜模数没有单位根,考虑 ω3=ei2π3=12+i32,设 i2=3 扩域即可。

O(3n3log3c)

注意基尔霍夫矩阵是度数矩阵减掉邻接矩阵,这里 u 的度数指的是所有与其相邻点的边权和!!邻接矩阵 a[u,v]u,v 的边权!!

lg-blog

[ARC096C] Everything on It

考虑容斥,钦点 k 个数字出现了不足两次,然后枚举这 k 个数字出现在了 i 个选出的子集里面,应该是:

k=0n(1)k(nk)22nkj=0k(kj)i=1j{ji}(2nk)i

=k=0n(1)k(nk)22nki=1k(2nk)ij=ik(kj){ji}

注意有 k(nk){km}={n+1m+1}

考虑组合意义,前面是“先从 n 数中选出若干,然后分到 m 个集合里”。可以认为剩下的元素被分到了垃圾堆,由于不能留空集,因此再加入一个元素,答案就是 {n+1m+1}

=k=0n(1)k(nk)22nki=1k(2nk)i{k+1i+1}

就是 O(n2)

[CF1295F] Good Contest

考虑将值域按照区间的起点化成若干段。比如 [1,3][5,8][9,10] 就把值域划分成了 [0,1),[1,4),[4,5)[5,9)[9,11) 这些段。

f[i,j] 表示考虑前 i 个位置,最后一个位置落在 j 之后的段的方案数。考虑枚举 j 这一个数字段影响的范围是 [k,i],k[1,i],那么转移是 f[i,j]f[k1,j+1](lenj+ikik+1),还需要满足 [k,i] 的所有数字均可以选在第 j 段内。

转移系数是 g[i]=(T+ii+1) 的形式,有 g[0]=T,g[i]=T+ii+1g[i1],枚举 j 之后直接预处理即可。

O(n3)

.

24

训练 34 C

考虑一个简单问题,给定一个序列 a 和阈值 k,要求 a 的任意一个子段和都不大于 k。可以花费 1 的代价将任意一个位置减一,问最小花费多少代价。

考虑对每个右端点 i,考虑一个使得 sum(j,i) 最大的 j,只需要在 i 这个位置把 sum(j,i) 超过 k 的部分减掉就好了。感性理解一下这样贪很对,然后就有了线性做法。

往上套区间查询??

训练 34 B

考虑先建出广义 SAM,然后拿 SAM 读入一个串 s,从经过的每个点向上跳 nxt 链,经过的总点数和是均摊 O(|s||s|)

也就是说,我从每个读入位置向上暴力跳链,跳过的位置不跳,这样的复杂度是 O(|s||s|)。然后 BIT 大力就是 50,改成差分草了 80.../jk

考虑每次向上覆盖颜色,实际上是等价于一个 access,然后就是树点涂色这个题,直接大力树剖覆盖难写的跟 shi 一样。

考虑拿 LCT 维护这个东西,实链存一些点到根之间的同色段,然后一次修改就直接大力 access 改上去,拿个数组差分解决这个东西,就是 O(nlogn)

训练 34 A

考虑如果斜率都知道,那么这题就做完了,然后爆搜就是 50pts.

考虑如果按照 |xi/yiyi/xi| 排序的话,那么最中间的向量一定是最靠前的那个,之后的每一个一定在凸包的左边或者右边扩展。然后就可以 DP?

一个向量有两个可能的 tan,用最大的那个排序就好了,之后直接 DP 也是对的/fad 玄学...

[CF618E] Robot Arm

线段树维护一些向量形如 vi=(xi,yi),然后对于最底层节点单独维护一个辐角形式 λi=(θi,li),然后单点改就直接下放到最底层改 λi,然后更新 vi,然后合并上去,就没了。

错了。一次修改不止改了一个向量,应该是一个后缀的所有向量做旋转笛卡尔系。

每次以 y 个向量的起始为坐标原点,在笛卡尔系内旋转向量。

把一个系内的向量,以坐标系为参考,逆时针旋转 θ 角的旋转矩阵是:

M(θ)=|cosθsinθsinθcosθ|

也就是 |xy|M(θ)=|xy|,推导可以直接考虑辐角形式,然后恒等变换搞出来。

所以直接后缀打矩阵 tag 即可。

[AGC034F] RNG and XOR

min-max 容斥。

考虑先算选出 s,is 的期望次数是 E(i),那就枚举一个 i 的子集 T,需要计算 P(T)=jTP(j)=1jTP(j),有:

E(i)=Ti,T(1)|T|11/P(T)

E(i)=iSE(S)

那么子集反演:

E(i)=iS(1)|i||S|E(S)

以上均可以高维前缀和处理,复杂度 O(n2n)

错了!这么算不对,再 min-max 容斥一遍也不对!列方程是啥东西啊/kk

.

25

35 A

考虑把一个串合并到它的最小循环节上面去,然后剩下的串数实际上就是答案。也就是说,要求最小循环节等于本串的数的个数。

考虑长度为 n 的串一共有 cn 个。考虑减掉不合法的,就是枚举一个 d|n,d<n,减掉长度为 d 的最小循环节等于本串的数的个数,因为这些串中的每一个的若干次方都可以唯一对应一个不合法串。

还有一个小问题,就是长度为 n 的串之间的同构。容易发现这样减掉之后,每个本质不同串的每个轮换都被计算了一次贡献,所以再除掉 n 即可。

也就是有转移 f[n]=cnd|n,d<nf[d],答案是 i=1Lf[i]/i

狄利克雷卷积暴力计算的复杂度就是 O(nlnn),这已经很快了,大多数情况下是足够用的。但是在某些特殊情况下,这还可以进一步优化,这种情况是计算狄利克雷前缀和:

g[n]=k|nf[k]

i=kpkαk,j=kpkβk,那么 i 能贡献到 j 当且仅当 k,αkβk

然后发现这类似于高维前缀和,可以用每个素数单独转移,复杂度就是 O(nloglogn)

先枚举维数,然后从小到大枚举数字,做前缀和。注意必须从小到大,实际上就是这个维度上的前缀和。

整理一下三种变式:

这个好像不能做/kk

后面两个是半在线的,注意区分一下。

35 C

冷静一下,发现需要求 s 的每个前缀的本质不同子串数,s 的每个前缀 s(s)r 的共同本质不同子串数,s 的每个前缀的本质不同回文串数。

第一个和第三个都很好求,考虑第二个。

第一种思路是对 s(s)r 建立广义 SAM,这个显然不能做到低于 O(n2)

第二种思路是拿 s 的 SAM 读入 (s)r,然后考虑每个位置的贡献。这个位置的贡献需要维护 (s)r 的 SAM,同时维护当前的读入长度 l 和在 SAM 上的位置 u,那么贡献就是 max0,(minlen[i],l)len[nxt[u]]。但是显然也没法做到低于 O(n2)

[CF1264D2] Beautiful Bracket Sequence

考虑给定一个括号串,如何求它的深度。实际上就是找一个间隔,使得间隔左边的左括号个数等于间隔右边的右括号个数,然后答案就是间隔左边的左括号个数。

那么直接 DP,设 f[i,j] 表示前缀 ij 个左括号的方案数,转移是直接的。枚举一个 i,j,把 f[i,j]·g[i+1,j] 算到答案里面即可。复杂度 O(n2)

考虑实际上不需要 DP,枚举一个位置 i,前后的转移系数是:

jj(pc[i]jpre[i])(sc[i+1]jsuf[i+1])

pre[i]i 前面的左括号个数,suf[i]i 后面的右括号个数,pc[i]i 前面的问号个数,sc[i]i 后面的问号个数。

换下枚举指标,实际上等于:

pre[i](pc[i]+sc[i+1]pc[i]+pre[i]suf[i+1])+pc[i](pc[i]+sc[i+1]1pc[i]+pre[i]suf[i+1])

.

26

幂级数的收敛域和收敛半径:zhihu

等比级数的闭合形式,亦即数列 <1,1,1,...> 的 OGF 对矩阵存在解析意义,也就是:

i0Mi=IIM

这个还是记住吧...

求逆方式 zhihu:将单位矩阵拼在 A 后面得到增广矩阵,然后通过行列变换将前一个矩阵消成单位矩阵,此时后面的矩阵就是 A 的逆矩阵。

A 的逆矩阵等于 A 伴随矩阵除以 A 的行列式。所以我们有了一个计算伴随矩阵和代数余子式的 O(n3) 做法:先求 A 的逆,然后乘上 A 的行列式。

行列式为零等价于有一行没有主元,这个可以直接在高斯消元的时候判断。

36 B

考虑递推式:

an=xan1ybn1an=xbn1+yan1

边界是 a0=1,b0=0,求 i=0maibici 的值。 m 可能为 ,此时需要判断幂级数是否收敛,并求它的收敛域。

显然矩阵求逆随便解决任何 m 的情况,但是注意矩阵不存在逆的时候,我们并没有办法判断这个东西是否收敛,以及求它的收敛域,这是矩阵逆的性质导致的。

考虑这种二元递推关系,把它表示称复数的形式 zn=an+bni,那么 zn+1=(xanybn)+(xbn+yan)i,有 zn+1/zn=(x+yi)

好了因为这个优雅的性质,这题可以用另一种途径做,因为 an=Re(x+yi)n,bn=Im(x+yi)n,这是一个类似于多元生成函数的性质,我们尝试代入求和然后直接求出一个闭合形式。

[(x+yi)n]2=(an+bni)2=an2bn2+2anbni

12i=0mIm(x+yi)2ncn=12Imi=0mzn=12Im1zn+11z

这是有限情况,其中 z=[(x2y2)+2xyi]/c,这样有限随便做。

无限情况下,有闭合形式 12Im11z,这个形式的收敛半径是 (1,1)

级数收敛等价于上式虚部收敛,等价于 |z|<1

如果 |z|1 那么直接输出 error,否则直接套柿子求逆。注意复数求逆也满足费马小定理之类的规律,也就是可以直接拿共轭那一套来求逆,也可以直接快速幂。

另一个点,求 i=0nai,可以奇偶分类:

复杂度严格单 log

36 C

考虑给出一条链,求有多少个三元组 (i,j,k) 满足 i<j<kai+ak=aj

考虑分块,每 B 个元素分成一块,枚举中间元素 j,然后分类讨论:

  1. i,j,k 都在同一个块内:直接处理一边的桶,另一边暴力枚举计算,总复杂度 O(nB)
  2. i,j,k 中有一个和 j 在同一块内:维护前后缀块的桶,然后枚举一个暴力计算,总复杂度 O(nB)
  3. i,j,ki,kj 均不在同一块中:把两边的块直接卷积,总复杂度 O(nBmlogm)

因此这样复杂度就是 O(nB+nBmlogm)Bmlogm 时取得最优复杂度 O(nmlogm)

依然很卡常。

.

27

一个串的本质不同子串数量就是 O(n2) 级别的,没有更低的上界!

但是暴力跳 nxt[] 链可能会有一些奇怪的复杂度...

NOI OL A

数列:0110100110010110...

的分布规律是,popcount(x)%2=1 的位置是某种数字,popcount(x)%2=0 的位置是另一种数字。

还需要一个结论:

考虑一个 60pts 的做法,设 g[i,j,0/1] 表示前 2i 个数字,0/1 的部分,的 j 次方之和,考虑转移:

g[i+1,j,0]=g[i,j,0]+t=0j(jt)2i(jt)g[i,t,1]

这样可以 O(nk2) 的求出所有 g[] 的值。

考虑设 f(i,j,0/1,d) 表示将 g[i,j,0/1] 整体右移 d 个位置,有:

f(i,j,0/1,d)=t=0j(jt)djtg[i,t,1/0]

注意这里 0/1 恰好反转。然后就能拼出答案了。

预处理 S[i,j]=t=02i1tj,那么 g[i,j,0]=g[i,j,1]=S[i,j]2(ij)

ikg[] 可以 O(k3) 预处理出来,空间 O(k2)

对于 i>kg[],直接插出来是 O(k),然后复杂度爆炸。预处理是 O(nk+k3),大概有 80pts。不会/kk

.

29

NOIO / NOIP 答辩题选做

[NOIO2021TG A] 愤怒的小 N

N=2n,答案是 i=0N1f(i)[pop[i]mod2=1]。这样拆分:

2ans=i=0N1f(i)i=0N1(1)pop[i]f(i)=AB

前面是自然数幂和问题:

A=j=0k1aji=0N1ij=j=0k1ajt=0j{jt}t!i=0N1(it)

=j=0k1ajt=0j{jt}Nt+1t+1

预处理 N 的下降幂,直接计算就是 O(k2)

考虑后面,考虑一个分治的过程,即从高向低枚举 n 的每个有效位 x,需要算出从上一次的边界开始的 2x 个位置的答案,然后向右边递归分治(实际上循环模拟即可)。

g[i,j,0/1] 表示前 2i 个位置,所有 0/1 的位置的 j 次方之和,有转移:

g[i,j,0/1]=g[i1,j,0/1]+t=0j(tj)2(i1)tg[i1,jt,1/0]

设考虑左边界是 d,算 2x 个位置的 B 式,并且前面算过的段数的奇偶性是 o 的答案是 sum(d,x,o),那么有:

sum(d,x,o)=j=0k1ajt=0j(jt)dt(g[x,jt,o]g[x,jt,o1])

注意到当 xk 的时候,对所有 t[0,k1] 满足 g[x,t,0]=g[x,t,1],也就是 sum(d,x,o)=0,这时候直接 return 0 即可。

这样实际上只有 k 个位置算了贡献,总复杂度就是 O(n+k3)

[NOIO2021TG C] 岛屿探险

考虑如果 minbi,d=d,那么相当于查询区间内满足 aicdai 有多少,这是经典问题。

建立可持久化 Trie,然后讨论:

  1. 如果这一位上 c,d 都是 1,那么右子树都可以,递归左子树;
  2. 如果这一位上 c1d0,那么只能右子树;
  3. 如果这一位上 c0d1,那么左子树都可以,递归右子树;
  4. 如果这一位上 c,d 都是 0,那么只能左子树。

考虑如果 minbi,d=bi 怎么做?考虑对于一个 (ai,bi) 能贡献给哪些 c

可以枚举使得 aicbi 的第一个位置,就可以确定 c 的一些高位数字,放在 Trie 树上就对应一个节点。考虑拿 Tire 插入二元组 (ai,bi),然后讨论:

  1. bi 这一位为 0,那么这个高位没有贡献,递归左子树;
  2. bi 这一位为 1,那么这个高位在 ai 这一位对应的子树有贡献,递归另一个子树。

答案就是插入 c 的过程中走过的那条链的和。实际上这个做法是对 c 建立了 Trie 然后考虑贡献。

这样就有大概 55pts.

考虑线段树分治,先离线询问挂在线段树上,那么每个节点都是整段询问,把它们按照 d 排序。

然后对每个节点单独做,就是直接把 (ai,bi) 按照 bi 排序。这样线段树一共有 logn 层,每层有 n 个元素,建立 Trie 和查询均需要 O(ω) 的时间,因此复杂度是 O((n+q)lognω)

.

30

[HDU5390] Tree

总结下拿线段树分治解决可持久化问题的思路。

这道题首先树剖,然后询问拆成 O(nlog2n) 个。然后对于线段树上每个节点,直接维护它的操作序列,那么一次修改,会修改线段树上 O(logn) 层每层的一个节点,也就是在操作序列里面加一项“删除...插入...”。

最后拿一棵 Trie 去遍历线段树结构,不需要可持久化,直接枚举询问,顺序执行操作序列,复杂度 O(nlog2nω),空间 O(nω)

树剖常数小,大力松一松。

solu

[LG P5807] Which Dreamed It

有向图的欧拉回路存在当且仅当每个点的入度等于出度。几个计数定理:

这里欧拉图指存在欧拉回路的图,默认不允许存在空点。两条欧拉回路不同,当且仅当经过边形成的环旋转不同构。

无向图的基尔霍夫矩阵是“每个点相邻边的权值和矩阵”减去边权邻接矩阵。

有向图类似:如果要算外向树,那么相邻边只统计入边;否则只统计出边。

模数是质数!!1

[JSOI2018] 战争

首先存在两个三角形有交就一定存在两个四边形有交....然后等价于两个凸包有交。

考虑求凸包 B 位移 d和凸包 B 有交,当且仅当 aA,bB,b+d=a

那么可行的 d 应当落在一个凸包 D 内,满足 D 的点集是 A,(B) 的闵可夫斯基和。

上面这个结论指出了这个凸包上的点数是 O(|A|+|B|) 的。

考虑如何求出这个凸包,可以发现这个凸包就是把两个凸包上的边极角排序之后顺次连接起来。先把两个凸包都用向量表示,然后把向量合起来极角排序,定义象限序为“四 < 一 < 二 < 三”然后排序,然后维护出和凸包横坐标最小的那个点,然后按照排序后的向量转一圈就求出来了。

考虑如何判断一个点在凸包内部,找到这个点横坐标处的上凸壳上的边和下凸壳上的边即可,然后叉积随便搞搞。

写麻烦了......

定义点的大小是先按 x 升序再按 y 降序,凸包从下凸壳转到上凸壳。

求闵可夫斯基和可以直接维护出两个凸包的一圈点,然后归并。凸包上的第一个点一定是 c1=a1+b1,接下来的点比较那条向量比较靠下即可。

判断一个点在凸包内部,可以把凸包上所有点和查询点都减去第一个点的坐标。这样凸包上所有点在一个半平面内且按照极角序排列,可以直接二分找到现在查询点在哪一个三角剖分里面,就可以判断了。

注意可以在凸包后面多留一个点(也就是第一个点)来避免 border case。

O(n+m+qlognm)

.

31

争取字数破 3w!

38 B

现在有 O(nm) 个 01 方程,有 O(m) 个变量,每个方程只有 O(1) 个位置是有效的,现在要判断方程是否有解。

考虑维护最简形式的线性基,然后加入一个向量。因为我们只需要对每个 1 所在的位置,确定这个位置是否有主元;如果没有,则确定主元并向上下消元。

确定主元一共只会进行 O(m) 次,每次消元的复杂度是 O(m2ω),这部分的复杂度是 O(m3ω)。对每个向量,用 bitset::_Find_first() 和 bitset::_Find_next() 遍历所有 1 的位置是 O(mω+popcount) 的,因此总复杂度是 O(nm2ω+m3ω) 的。

考虑判断有解,当且仅当所有未插入线性基的方程消元结束之后等号右边是零。

这一类复杂度可以这样分析:一共有 O(n2) 个 1,对每个 1 消去它需要 O(nω) 的复杂度;一共会进行 O(n) 次消元,每次的复杂度是 O(n2ω)

这样在线维护比离线高斯消元的复杂度要优。

结论:任意一个八个方块的子矩形,如果都满足外围格子去掉四个角的异或和是零,那么就可以。

38 A

首先我们求所有情况下,从 1 到所有点的最短路之和,最后结果除 n 就是答案。

考虑对着最短路树 DP,设 f[d,i,j] 表示 i 个点的图,考虑到了最短路树的第 d 层,第 d 层有 j 个点的方案数;g[d,i,j] 表示边权和。转移:

f[d,i,j]=k=1ij(i1j)f[d1,ij,k](2k1)j2(j2)

g[d,i,j]=k=1ij(i1j)(2k1)j2(j2)(g[d1,ij,k]+jdf[d1,ij,k])

标号重分配!!!

考虑压状态,选择一个出现次数比较小,影响比较小的变量,然后对这个变量的所有求和一起 DP。这里选择 d

F[i,j]=df[d,i,j]=k=1ij(i1j)(2k1)j2(j2)F[ij,k]

G[i,j]=dg[d,i,j]

=k=1ij(i1j)(2k1)j2(j2)G[ij,k]+k=1ij(i1j)(2k1)jjddf[d1,ij,k]

后面不好处理,再添加状态,设 Fd[i,j]=ddf[d,i,j],后面的转移是:

G[i,j]=k=1ij(i1j)(2k1)j2(j2)G[ij,k]+k=1ij(i1j)(2k1)j2(j2)j(Fd[ij,k]+F[ij,k])

Fd[] 的转移是:

Fd[i,j]=ddf[d,i,j]=k=1ij(i1j)(2k1)j2(j2)(Fd[ij,k]+F[ij,k])

边界是 F[1,1]=1,Fd[1,1]=G[1,1]=0,答案是 1n1jG[n,j]

[LG P4195] 扩展BSGS

exBSGS

之前想到过为什么适用性会和模数的素性有关,当时感性的给出了一个解释,现在看来好像犯了一个傻.....

重新理性推导一遍。BSGS 基于这个等价转换:

证明是显然的,只需要满足 k 的取值上界 U 可以使得 UB2φ(P)

等价于:

既然是必要的那么只需要检验一下就可以解决充分性问题。还有一个问题是模数的倍数无法区分,这个只需要把数字改写成 (i,j)=iPj 的形式即可。

玄学,弃了。

.